package main.Q1401_1500;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Q1441_1450 {
    public static void main(String[] args) {
        System.out.println("Question1441：用栈操作构建数组");
        System.out.println("Question1442：形成两个异或相等数组的三元组数目");
        System.out.println("Question1443：");
        System.out.println("Question1444：");
        System.out.println("Question1445：");
        System.out.println("Question1446：");
        System.out.println("Question1447：最简分数");
        System.out.println("Question1448：统计二叉树中好节点的数目");
        System.out.println("Question1449：");
        System.out.println("Question1450：");
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Question1441 {
    public List<String> buildArray(int[] target, int n) {
        List<String> result = new ArrayList<>();
        Stack<Integer> temp = new Stack<>();
        int index = 0;
        for (int i = 1; i <= n && index < target.length; i++) {
            if (i < target[index]) {//入栈数小于目标数
                temp.add(i);
                result.add("Push");
                continue;
            }
            if (i == target[index]) {
                if (index != 0) {
                    while (!temp.isEmpty() && index != 0 && temp.peek() != target[index - 1]) {//多余元素出栈
                        temp.pop();
                        result.add("Pop");
                    }
                } else {
                    while (!temp.isEmpty()) {//多余元素出栈
                        temp.pop();
                        result.add("Pop");
                    }
                }
                temp.add(i);
                result.add("Push");
                index++;
            }
        }
        return result;
    }
}

class Question1442 {
    public int countTriplets(int[] arr) {
        int count = 0;
        int[] dp = new int[arr.length];
        dp[0] = arr[0];
        for (int i = 1; i < arr.length; i++) {
            dp[i] = dp[i - 1] ^ arr[i];
        }
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                for (int k = j; k < arr.length; k++) {
                    int a = 0, b = 0;
                    if (i == 0) {
                        a = dp[j - 1];
                    } else {
                        a = dp[j - 1] ^ dp[i - 1];
                    }
                    b = dp[k] ^ dp[j - 1];
                    if (a == b) {
                        count++;
                    }
                }
            }
        }
        return count;
    }
}

class Question1447 {
    public int process(int a, int b) {
        if (a % b == 0) {
            return b;
        }
        return process(b, a % b);
    }

    public List<String> simplifiedFractions(int n) {
        List<String> result = new ArrayList<>();
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                int temp = process(j, i);
                if (temp == 1) {
                    result.add(j + "/" + i);
                }
            }
        }
        return result;
    }
}

class Question1448 {
    int count = 0, max = Integer.MIN_VALUE;

    public int goodNodes(TreeNode root) {
        if (root != null) {
            if (root.val >= max) {
                count++;
                max = root.val;
            }
            int temp = max;
            goodNodes(root.left);
            max = temp;// 子树完成，回退当前节点
            goodNodes(root.right);
        }
        return count;
    }
}